package ch2.app.array;

import java.util.*;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;

class PolyClass {        //多项式顺序表类
    ArrayList<PolyElem> poly;    //存放多项式顺序表

    public PolyClass() {    //构造方法
        poly = new ArrayList<PolyElem>();    //分配顺序表的data空间
    }
    //包含Add、CreatePoly、Sort和DispPoly方法

    public void Add(PolyElem p) {    //末尾添加一个多项式项
        poly.add(p);
    }

    public void CreatePoly(double[] coef, int[] exp, int n) { //建立多项式顺序表
        for (int i = 0; i < n; i++) {
            poly.add(new PolyElem(coef[i], exp[i]));
        }
    }

    public void Sort() {    //对多项式顺序表按exp域递减排序
        poly.sort(Comparator.comparing(PolyElem::getExp).reversed());    //comparingInt
    }

    public void DispPoly() {    //输出多项式顺序表
        boolean first = true;        //first为true表示是第一项
        int i = 0;
        while (i < poly.size()) {
            PolyElem p = poly.get(i);
            if (first) {
                first = false;
            } else if (p.coef > 0) {
                System.out.print("+");
            }
            if (p.exp == 0) {  //指数为0时不输出'x'
                System.out.print(p.coef);
            } else if (p.exp == 1) {    //指数为1时不输出指数
                System.out.print(p.coef + "x");
            } else {
                System.out.print(p.coef + "x^" + p.exp);
            }
            i++;
        }
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < poly.size(); i++) {
            PolyElem elem = poly.get(i);
            // coef>0添加+
            if (elem.coef > 0) {
                sb.append("+");
            }
            // 分成三种情况：exp=0、exp=1和exp>0
            if (elem.exp == 0) {
                sb.append(elem.coef);
            } else if (elem.exp == 1) {
                sb.append(elem.coef).append("X");
            } else {
                sb.append(elem.coef).append("X^").append(elem.exp);
            }

        }
        String result = sb.toString();
        if (result.startsWith("+")) {
            result = sb.substring(1);
        }
        return result;
    }
}

public class PolyTest {
    // 有序顺序表的二路归并
    public static PolyClass Add(PolyClass L1, PolyClass L2) {  //两个多项式相加运算
        // 1. 初始化
        int i = 0, j = 0;
        double c;
        PolyClass L3 = new PolyClass(); //新建L3的元素
        // 2. 遍历顺序表
        while (i < L1.poly.size() && j < L2.poly.size()) {
            if (L1.poly.get(i).exp > L2.poly.get(j).exp) {
                //L1的元素的指数较大
                L3.Add(new PolyElem(L1.poly.get(i).coef, L1.poly.get(i).exp));  //新建L3的元素
                i++;
            } else if (L1.poly.get(i).exp < L2.poly.get(j).exp) {
                //L2的元素的指数较大
                L3.Add(new PolyElem(L2.poly.get(j).coef, L2.poly.get(j).exp));    //新建L3的元素
                j++;
            } else {
                //l1和l2的指数相等
                c = L1.poly.get(i).coef + L2.poly.get(j).coef;  //求两指数相等元素的系数和
                if (c != 0) {   //系数和c不为0时复制
                    L3.Add(new PolyElem(c, L1.poly.get(i).exp));
                }
                i++;
                j++;
            }
        }
        // 3. 判断l1、l2是否已经遍历完，没有就把剩余的元素增加到l3的后面
        while (i < L1.poly.size()) {    //复制l1余下的元素
            L3.Add(new PolyElem(L1.poly.get(i).coef, L1.poly.get(i).exp));  //新建L3的元素
            i++;
        }
        while (j < L2.poly.size()) {   //复制l2余下的元素
            L3.Add(new PolyElem(L2.poly.get(j).coef, L2.poly.get(j).exp));  //新建L3的元素
            j++;
        }
        return L3;
    }

    public static void main(String[] args) throws FileNotFoundException {
        // 1. 重定向标准输入、输出流到abc.in、abc.out
        // 使用Intellij IDEA编译运行的文件路径
        System.setIn(new FileInputStream("resource/ch2/abc.in"));
        Scanner fin = new Scanner(System.in);
        System.setOut(new PrintStream("resource/ch2/abc.out"));  //将标准输出流重定向至abc

        // 2. 初始化
        PolyClass L1 = new PolyClass();
        PolyClass L2 = new PolyClass();
        PolyClass L3;                   //建立3个多项式顺序表对象
        double[] a = new double[100];
        int[] b = new int[100];
        int n;

        // 3. 创建两个多项式
        n = fin.nextInt();              //输入n
        for (int i = 0; i < n; i++) {   //输入a
            a[i] = fin.nextDouble();
        }
        for (int i = 0; i < n; i++) {   //输入b
            b[i] = fin.nextInt();
        }
        L1.CreatePoly(a, b, n);         //创建第1个多项式顺序表
        System.out.print("第1个多项式:  ");
        L1.DispPoly();

        n = fin.nextInt();              //输入n
        for (int i = 0; i < n; i++) {   //输入a
            a[i] = fin.nextDouble();
        }
        for (int i = 0; i < n; i++) {   //输入b
            b[i] = fin.nextInt();
        }
        L2.CreatePoly(a, b, n);         //创建第2个多项式顺序表
        System.out.print("第2个多项式:  ");
        L2.DispPoly();

        // 4. 两个多项式排序
        L1.Sort();  //排序
        System.out.print("L1排序后:   ");
        L1.DispPoly();

        L2.Sort();                      //排序
        System.out.print("L2排序后:   ");
        L2.DispPoly();

        // 5. 两个多项式相加
        L3 = Add(L1, L2);               //两多项式相加
        System.out.print("多项式相加后: ");
        L3.DispPoly();
    }
}

// 设置abc.in的路径： System.setIn(new FileInputStream("./ch2/app/array/abc.in"));
// 打开Terminal，切换到src目录，运行以下命令
// javac -encoding utf8 .\ch2\app\array\PolyTest1.java
// java ch2.app.array.PolyTest1

